#include<iostream>

using std::cout;
using std::endl;

template<class T>
struct List_Node
{
    struct List_Node<T>* _prev;
    struct List_Node<T>* _next;
    T _val;

    List_Node(const T& val=T())//形参传递给val是构造
    :_prev(nullptr)
    ,_next(nullptr)
    ,_val(val)//val传递给_val是拷贝构造
    {}
};

template<class T,class Ref,class Ptr>
struct __list_iterator
{
    typedef struct List_Node<T> node;
public:
    typedef struct __list_iterator<T,Ref,Ptr> self;
    //构造函数
    __list_iterator(node* it)
    {
        _node=it;
    }

    // __list_iterator(const self& it)
    // {
    //     _node=it._node;
    // }

    self& operator++()
    {
        _node=_node->_next;
        return _node;
    }
    self operator++(int)//tmp是局部对象，不可传引用返回
    {
        self tmp(*this);
        _node=_node->_next;
        return tmp;
    }

    self& operator--()
    {
        _node=_node->_prev;
        return _node;
    }
    self operator--(int)//tmp是局部对象，不可传引用返回
    {
        self tmp(*this);
        _node=_node->_prev;
        return tmp;
    }

    Ref operator*()
    {
        return _node->_val;
    }

    Ptr operator->()
    {
        return &(_node->_val);
    }

    bool operator!=(const self& it)const//注意，此处传来的it可能是一个临时对象，而临时对象具有常性
    {
        return _node!=it._node;
    }

    bool operator==(const self& it)const
    {
        return _node==it._node;
    }


private:
    node* _node=nullptr;//内置类型，浅拷贝
};

template<class T>
class list
{
    typedef List_Node<T> node;
public:
    typedef struct __list_iterator<T,T&,T*> iterator;
    typedef struct __list_iterator<T,const T&,const T*> const_iterator;

    iterator begin()
    {
        //return iterator(_head->_next)
        return _head->_next;//单参数的构造函数支持隐式类型转换   构造+拷贝构造
    }
    iterator end()
    {
        return _head;
    }
    const_iterator begin()const
    {
        return _head->_next;
    }
    const_iterator end()const
    {
        return _head;
    }

    list()
    {
        _head=new node();

        _head->_next=_head;
        _head->_prev=_head;
    }
    // list(const list<T>& lst)
    // {
    //     _head=new node();

    //     const_iterator it=lst.begin();
    //     while(it!=lst.end())
    //         push_back(*it);
    // }

    void Print()
    {
        node* tmp=_head->_next;
        while(tmp!=_head)
        {
            cout<<tmp->_val<<" ";
            tmp=tmp->_next;
        }
        cout<<endl;
    }

    iterator insert(iterator pos,const T& val)
    {
        node* newnode=new node(val);

        newnode->_prev=pos._node->_prev;
        newnode->_next=pos._node;

        pos._node->_prev->_next=newnode;
        pos._node->_prev=newnode;

        _size++;

        return newnode;
    }

    void push_back(const T& val)
    {
        node* newnode=new node(val);
        node* tail=_head->_prev;//尾结点

        newnode->_prev=tail;
        newnode->_next=_head;

        tail->_next=newnode;
        _head->_prev=newnode;

        _size++;
    }

    void push_front(const T& val)
    {
        insert(begin(),val);
    }

    void pop_back()
    {
        erase(_head->prev);
    }

    void pop_front()
    {
        erase(begin());
    }

    size_t size()
    {
        return _size;
    }

    iterator erase(iterator pos)
    {
        node* ret=pos._node->_next;
        if(pos==end())
        {
            cout<<"出错!!!"<<endl;
            return;
        }
        pos._node->_prev=pos._node->_prev;
        pos._node->_prev->_next=pos._node->_next;

        delete pos._node;
        pos._node=nullptr;

        _size--;

        return ret;
    }

    void clear()
    {
        iterator it=begin()
        while(it!=end())
            it=erase(it);
        _size=0;
    }

    ~list()
    {
        node* next=_head->_next;
        while(next!=_head)
        {
            node* tmp=next->_next;
            delete next;
            next=tmp;
        }
        delete _head;
        _head=nullptr;
        _size=0;
    }
private:
    node* _head=nullptr;//哨兵卫
    size_t _size=0;
};